// @algorithm @lc id=100306 lang=cpp
// @title zhan-de-ya-ru-dan-chu-xu-lie-lcof

#include "algm/algm.h"
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped) {
        stack<int> s;
        int n = pushed.size();
        if (n == 0) {
            return true;
        }
        int pushIndex = 0, popIndex = 0;
        while (popIndex < n) {
            // 栈为空
            if (s.empty()) {
                if (pushIndex < n) {
                    s.push(pushed[pushIndex]);
                    ++pushIndex;
                }
                else {
                    return false;
                }
            }
            // 栈非空
            else {
                // 可以弹出
                if (s.top() == popped[popIndex]) {
                    s.pop();
                    ++popIndex;
                }
                // 不能弹出，可以push
                else if (pushIndex < n) {
                    s.push(pushed[pushIndex]);
                    ++pushIndex;
                }
                // 没有元素可以push，但还没pop完
                else {
                    return false;
                }
            }
        }
        return true;
    }
};